By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 26, Issue 1, pp. 1-290

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

The Average-Case Complexity of Determining the Majority

Laurent Alonso, Edward M. Reingold, and René Schott

pp. 1-14

BibTeX  Abstract Full Text:  PDF

Amplification by Read-Once Formulas

Moshe Dubiner and Uri Zwick

pp. 15-38

BibTeX  Abstract Full Text:  PDF

Minimal Ascending and Descending Tree Automata

Maurice Nivant and Andreas Podelski

pp. 39-58

BibTeX  Abstract Full Text:  PDF

Threshold Computation and Cryptographic Security

Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf

pp. 59-78

BibTeX  Abstract Full Text:  PDF

Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs

Zhengyu Ge and S. Louis Hakimi

pp. 79-92

BibTeX  Abstract Full Text:  PDF

Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle

Endre Boros, Peter L. Hammer, Toshihide Ibaraki, and Kazuhiko Kawakami

pp. 93-109

BibTeX  Abstract Full Text:  PDF

Navigating in Unfamiliar Geometric Terrain

Avrim Blum, Prabhakar Raghavan, and Baruch Schieber

pp. 110-137

BibTeX  Abstract Full Text:  PDF

Finite Monoids: From Word to Circuit Evaluation

Martin Beaudry, Pierre McKenzie, Pierre Péladeau, and Denis Thérien

pp. 138-152

BibTeX  Abstract Full Text:  PDF

Parallelism Always Helps

Louis Mak

pp. 153-172

BibTeX  Abstract Full Text:  PDF

Stochastic Scheduling with Variable Profile and Precedence Constraints

Zhen Liu and Eric Sanlaville

pp. 173-187

BibTeX  Abstract Full Text:  PDF

On Bounded Queries and Approximation

Richard Chang, William I. Gasarch, and Carsten Lund

pp. 188-209

BibTeX  Abstract Full Text:  PDF

Sparse Dynamic Programming for Evolutionary-Tree Comparison

Martin Farach and Mikkel Thorup

pp. 210-230

BibTeX  Abstract Full Text:  PDF

Total Protection of Analytic-Invariant Information in Cross-Tabulated Tables

Ming-Yang Kao

pp. 231-242

BibTeX  Abstract Full Text:  PDF

On the Power of Real Turing Machines over Binary Inputs

Felipe Cucker and Dima Grigoriev

pp. 243-254

BibTeX  Abstract Full Text:  PDF

An $\NC$ Algorithm for Minimum Cuts

David R. Karger and Rajeev Motwani

pp. 255-272

BibTeX  Abstract Full Text:  PDF

Resource Bounds for Self-Stabilizing Message-Driven Protocols

Shlomi Dolev, Amos Israeli, and Shlomo Moran

pp. 273-290

BibTeX  Abstract Full Text:  PDF